package leetcode.code0105;

import leetcode.helper.tree.TreeNode;

public class Solution1 extends Solution105 {

	@Override
	public TreeNode buildTree(int[] preorder, int[] inorder) {
		return this.buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
	}

	private TreeNode buildTree(int[] preorder, int s1, int e1, int[] inorder, int s2, int e2) {
//		if (s1 > e1 || s2 > e2) {
//			return null;
//		}
		int rootVal = preorder[s1];
		TreeNode root = new TreeNode(rootVal);
		if (s1 == e1) {
			return root;
		}
		int index = s2;// 从s2开始，在inorder中找到rootVal。找头，inorder上index的左边是左子树上的，index右边是右子树上的
		while (index <= e2 && rootVal != inorder[index]) {
			index++;
		}
		int s = index - s2;// 左子树上有s个数，preorder上s1后s个数就是左子树的，剩余是右子树的
		if (s >= 1) {
			// [s1 + 1, s1 + s] 和 [s2, index - 1]
			root.left = this.buildTree(preorder, s1 + 1, s1 + s, inorder, s2, index - 1);
		}
		if (e1 >= s1 + s + 1) {
			// [s1 + s + 1, e1]
			root.right = this.buildTree(preorder, s1 + s + 1, e1, inorder, index + 1, e2);
		}
		return root;
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
//		so.debug1();
		so.debug2();
		so.debug3();
	}

}
